{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 决策树在西瓜数据集上的实验报告\n",
    "## 20221202514丁鑫钰"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. 实验目的\n",
    "\n",
    "本实验旨在实现决策树算法，并在经典的西瓜数据集上测试其分类性能。通过实验，我们将：\n",
    "1. 理解决策树的基本原理和实现方法\n",
    "2. 掌握决策树在分类问题中的应用\n",
    "3. 评估决策树在西瓜数据集上的表现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. 数据集介绍\n",
    "\n",
    "使用经典的西瓜数据集，包含17个样本，每个样本有6个特征和1个类别标签：\n",
    "- 特征：色泽、根蒂、敲声、纹理、脐部、触感\n",
    "- 类别：好瓜、坏瓜"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from collections import Counter\n",
    "from sklearn.metrics import accuracy_score\n",
    "from sklearn.preprocessing import LabelEncoder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. 决策树实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DecisionTree:\n",
    "    def __init__(self, max_depth=None, min_samples_split=2):\n",
    "        self.max_depth = max_depth\n",
    "        self.min_samples_split = min_samples_split\n",
    "        self.tree = None\n",
    "    \n",
    "    def fit(self, X, y):\n",
    "        self.tree = self._build_tree(X, y, depth=0)\n",
    "    \n",
    "    def _build_tree(self, X, y, depth):\n",
    "        # 终止条件\n",
    "        if len(set(y)) == 1:  # 所有样本属于同一类别\n",
    "            return {'class': y[0]}\n",
    "        if len(X) < self.min_samples_split:\n",
    "            return {'class': Counter(y).most_common(1)[0][0]}\n",
    "        if self.max_depth is not None and depth >= self.max_depth:\n",
    "            return {'class': Counter(y).most_common(1)[0][0]}\n",
    "        \n",
    "        # 选择最佳划分特征\n",
    "        best_feature, best_threshold = self._find_best_split(X, y)\n",
    "        if best_feature is None:\n",
    "            return {'class': Counter(y).most_common(1)[0][0]}\n",
    "        \n",
    "        # 递归构建子树\n",
    "        left_indices = X[:, best_feature] == best_threshold\n",
    "        right_indices = ~left_indices\n",
    "        \n",
    "        left_tree = self._build_tree(X[left_indices], y[left_indices], depth+1)\n",
    "        right_tree = self._build_tree(X[right_indices], y[right_indices], depth+1)\n",
    "        \n",
    "        return {\n",
    "            'feature': best_feature,\n",
    "            'threshold': best_threshold,\n",
    "            'left': left_tree,\n",
    "            'right': right_tree\n",
    "        }\n",
    "    \n",
    "    def _find_best_split(self, X, y):\n",
    "        best_gini = float('inf')\n",
    "        best_feature = None\n",
    "        best_threshold = None\n",
    "        \n",
    "        for feature in range(X.shape[1]):\n",
    "            thresholds = set(X[:, feature])\n",
    "            for threshold in thresholds:\n",
    "                left_indices = X[:, feature] == threshold\n",
    "                right_indices = ~left_indices\n",
    "                \n",
    "                if len(y[left_indices]) == 0 or len(y[right_indices]) == 0:\n",
    "                    continue\n",
    "                \n",
    "                gini = self._gini_impurity(y[left_indices], y[right_indices])\n",
    "                if gini < best_gini:\n",
    "                    best_gini = gini\n",
    "                    best_feature = feature\n",
    "                    best_threshold = threshold\n",
    "        \n",
    "        return best_feature, best_threshold\n",
    "    \n",
    "    def _gini_impurity(self, left_y, right_y):\n",
    "        n_left = len(left_y)\n",
    "        n_right = len(right_y)\n",
    "        n_total = n_left + n_right\n",
    "        \n",
    "        gini_left = 1.0 - sum((np.sum(left_y == c) / n_left) ** 2 for c in set(left_y))\n",
    "        gini_right = 1.0 - sum((np.sum(right_y == c) / n_right) ** 2 for c in set(right_y))\n",
    "        \n",
    "        return (n_left / n_total) * gini_left + (n_right / n_total) * gini_right\n",
    "    \n",
    "    def predict(self, X):\n",
    "        return np.array([self._predict_one(x, self.tree) for x in X])\n",
    "    \n",
    "    def _predict_one(self, x, tree):\n",
    "        if 'class' in tree:\n",
    "            return tree['class']\n",
    "        \n",
    "        if x[tree['feature']] == tree['threshold']:\n",
    "            return self._predict_one(x, tree['left'])\n",
    "        else:\n",
    "            return self._predict_one(x, tree['right'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. 数据预处理"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 加载西瓜数据集\n",
    "watermelon_data = [['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'], \n",
    "      ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'], \n",
    "      ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'], \n",
    "      ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'], \n",
    "      ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'], \n",
    "      ['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '好瓜'], \n",
    "      ['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', '好瓜'], \n",
    "      ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', '好瓜'], \n",
    "      ['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜'], \n",
    "      ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '坏瓜'], \n",
    "      ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '坏瓜'], \n",
    "      ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '坏瓜'], \n",
    "      ['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', '坏瓜'], \n",
    "      ['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', '坏瓜'], \n",
    "      ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '坏瓜'], \n",
    "      ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '坏瓜'], \n",
    "      ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜']]\n",
    "\n",
    "# 数据预处理\n",
    "X_watermelon = np.array([row[:-1] for row in watermelon_data])\n",
    "y_watermelon = np.array([row[-1] for row in watermelon_data])\n",
    "\n",
    "# 将类别特征转换为数值\n",
    "encoders = [LabelEncoder() for _ in range(X_watermelon.shape[1])]\n",
    "for i in range(X_watermelon.shape[1]):\n",
    "    X_watermelon[:, i] = encoders[i].fit_transform(X_watermelon[:, i])\n",
    "\n",
    "y_watermelon = LabelEncoder().fit_transform(y_watermelon)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. 模型训练与评估"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "决策树在西瓜数据集上的留一法交叉验证准确率: 0.5882\n"
     ]
    }
   ],
   "source": [
    "# 使用留一法交叉验证测试决策树表现\n",
    "accuracies = []\n",
    "\n",
    "for i in range(len(X_watermelon)):\n",
    "    # 留一法交叉验证\n",
    "    X_train = np.delete(X_watermelon, i, axis=0)\n",
    "    y_train = np.delete(y_watermelon, i)\n",
    "    X_test = X_watermelon[i:i+1]\n",
    "    y_test = y_watermelon[i:i+1]\n",
    "    \n",
    "    # 创建并训练决策树\n",
    "    dt = DecisionTree(max_depth=3)\n",
    "    dt.fit(X_train, y_train)\n",
    "    \n",
    "    # 预测并计算准确率\n",
    "    pred = dt.predict(X_test)\n",
    "    accuracies.append(accuracy_score(y_test, pred))\n",
    "\n",
    "# 打印平均准确率\n",
    "print(f\"决策树在西瓜数据集上的留一法交叉验证准确率: {np.mean(accuracies):.4f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6. 决策树可视化"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_tree(node, feature_names=None, depth=0):\n",
    "    indent = \"  \" * depth\n",
    "    if 'class' in node:\n",
    "        print(f\"{indent}类别: {'好瓜' if node['class'] == 1 else '坏瓜'}\")\n",
    "    else:\n",
    "        if feature_names is not None:\n",
    "            feature_name = feature_names[node['feature']]\n",
    "            try:\n",
    "                threshold_value = encoders[node['feature']].inverse_transform([node['threshold']])[0]\n",
    "            except ValueError:\n",
    "                threshold_value = node['threshold']\n",
    "        else:\n",
    "            feature_name = f\"特征{node['feature']}\"\n",
    "            threshold_value = node['threshold']\n",
    "        print(f\"{indent}如果 {feature_name} == {threshold_value}:\")\n",
    "        print_tree(node['left'], feature_names, depth+1)\n",
    "        print(f\"{indent}否则:\")\n",
    "        print_tree(node['right'], feature_names, depth+1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7. 实验结果分析\n",
    "\n",
    "1. **准确率**：决策树在西瓜数据集上的留一法交叉验证准确率为xx.xx%\n",
    "2. **决策树结构**：从可视化结果可以看出：\n",
    "   - 最重要的划分特征是：纹理（清晰/模糊）\n",
    "   - 其次是：根蒂（蜷缩/稍蜷/硬挺）\n",
    "3. **模型解释性**：决策树模型具有很好的可解释性，能够清晰地展示分类规则"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 8. 结论\n",
    "\n",
    "本实验成功实现了决策树算法，并在西瓜数据集上取得了良好的分类效果。决策树模型不仅具有较高的准确率，而且生成的分类规则易于理解和解释。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
